package com.leecode.xiehf.page_01;

import com.leecode.Printer;

import java.util.*;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * [1,2,1],
 * [2,1,1]]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/permutations-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0047 extends Printer {

    public static void main(String[] args) {
        Solution_0047 solution = new Solution_0047();
        List<List<Integer>> v = solution.permuteUnique(new int[]{1 , 2, 3});
        printIntList(v);
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> output = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] exist = new boolean[nums.length];
        this.backtrack(res, output, nums, 0, exist);
        return res;
    }

    private void backtrack(List<List<Integer>> res, List<Integer> output, int[] nums, int index, boolean[] exist) {
        if (index == nums.length) {
            res.add(new ArrayList<>(output));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (exist[i]
                    || (i > 0 && nums[i] == nums[i - 1] && !exist[i - 1])) {
                continue;
            }
            output.add(nums[i]);
            exist[i] = true;
            this.backtrack(res, output, nums, index + 1, exist);
            exist[i] = false;
            output.remove(index);
        }
    }

    public List<List<Integer>> permuteUnique1(int[] nums) {
        Map<String, List<Integer>> res = new HashMap<>();
        recursion(res, nums, 0);
        return new ArrayList<>(res.values());
    }

    private void recursion(Map<String, List<Integer>> res, int[] nums, int deep) {
        if (deep == nums.length) {
            List<Integer> list = new ArrayList<>();
            StringBuilder sb = new StringBuilder();
            for (int num : nums) {
                sb.append(num);
                list.add(num);
            }
            res.put(sb.toString(), list);
            return;
        }

        for (int i = deep; i < nums.length; i++) {
            if (deep < i) {
                int temp = nums[deep];
                nums[deep] = nums[i];
                nums[i] = temp;
            }
            recursion(res, nums, deep + 1);
            if (deep < i) {
                int temp = nums[deep];
                nums[deep] = nums[i];
                nums[i] = temp;
            }
        }
    }
}
